package org.niu.listnode;

import java.util.ArrayList;
import java.util.List;

public class ReorderList {
    public void reorderList(ListNode head) {
        ListNode newHead = new ListNode(-1);
        ListNode p = head,tail = newHead;
        List<Integer> list = new ArrayList<>();
        while(p!=null){
            list.add(p.val);
            p = p.next;
        }
        int i = 0,j = list.size()-1;
        while(i<=j){
            if(i!=j){
                ListNode tmp = new ListNode(list.get(i));
                ListNode tmp1 = new ListNode(list.get(j));
                tail.next = tmp;
                tmp.next = tmp1;
                tail = tail.next.next;
            }else{
                ListNode tmp = new ListNode(list.get(i));
                tail.next = tmp;
                tail = tail.next;
            }
            i++;
            j--;
        }
        head.next.next = newHead;
    }
}
